# 1. 写出一个函数def functer(var1:list, var2: int)，第一个参数是列表，第二个参数是数字，函数返回一个列表。返回的结果是var1内元素，且能够整除var2。

def functer(var1: list, var2: int) -> list:
    if isinstance(var1, list) and len(var1) != 0 and isinstance(var2, (int, float)) and var2 != 0:
        lst = list()
        for x in var1:
            if x % var2 == 0:
                lst.append(x)
    else:
        raise ValueError

    return lst


print(functer([1, 2, 3, 4, 5, 6], 1.222))

# 这个题目考察的是函数及参数的基本使用，如果要考虑异常情况，那要写的就很多了。
# 这个题目尝试一下使用列表解析式来完成看看。

# 2. 给定两个字符串，写一个函数，返回这两个字符串中最长的相同部分。例如"knowledge"和"known"相同的最长部分是"know"

# 方法1，暴力求解
# 最长公共字符串假定出现在短的字符串中（T），第一次使用最长的T与长串(S)进行比较，如果无法匹配，T串去掉一位再次进行比较，直到发现为止

def brute_force(S: str, T: str):
    """
    :param S: 较长字符串
    :param T: 模式串
    :return: 匹配的字符串
    """
    if len(T) > len(S):
        S, T = T, S

    length = len(T)
    result = []
    # abcd
    for step in range(length, 0, -1):
        for start in range(0, len(S)):
            flag = False
            tmp = T[start:start + step]
            if S.find(tmp) > -1:
                result.append(tmp)
                flag = True
                newstart = start + 1

                # 已经找到了最长子串，接下来查看是否还有相同长度的子串

                while flag:
                    if newstart + step > length:
                        break
                    newtemp = T[newstart:newstart + step]
                    if S.find(newtemp) > -1:
                        result.append(newtemp)
                        newstart += 1
                    else:
                        flag = False

    def get_max_length(src: list):
        max_length = 0
        return [max_length if len(x) < max_length else len(x) for x in src][0]

    return set(filter(lambda x: len(x) == get_max_length(result), result))


str1 = 'abcdefgg好好学习denf'
str2 = 'denf好好学习abcd'
lst = brute_force(str1, str2)
print(lst)

# 方法2，使用动态规划实现
# 创建一个二维矩阵

def dynamic_pro(S:str,T:str):
    """
    :param S: 字符串
    :param T: 模式串
    :return: str
    """
    len_s = len(S)
    len_t = len(T)

    matrix = [[0] * len_s for i in range(len_t)]

    xmax = 0
    xindex = 0

    for i, x in enumerate(T):

        for j,y in enumerate(S):
            if x == y:
                if i == 0 or j == 0:
                    matrix[i][j] = 1
                else:
                    matrix[i][j] = matrix[i-1][j-1] + 1
                if matrix[i][j] > xmax:
                    xmax = matrix[i][j]
                    xindex = j
    return S[xindex - xmax + 1: xindex+1]

print(dynamic_pro(str1,str2))

#如果同时存在多个相同长度的字串，二维矩阵的返回结果是否是随机性的？